package DataStructure.hash;

import java.util.*;

/**
 * 128. 最长连续序列
 */
public class LongestConsecutive {

    public static void main(String[] args) {
        new LongestConsecutive().longestConsecutive(new int[]{100,4,200,1,3,2});
    }
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        List<Integer> list = new ArrayList<>(nums.length);
        HashSet<Integer> hashSet = new HashSet<>(nums.length);
        for (int num : nums) {
            list.add(num);
            hashSet.add(num);
        }
        int maxLen = 0;
        for (Integer num : list) {
            if (!hashSet.contains(num)) continue;
            int len = 0;
            int i = num;
            while (hashSet.contains(i)) {
                len++;
                hashSet.remove(i++);
            }
            i = num - 1;
            while (hashSet.contains(i)) {
                len++;
                hashSet.remove(i--);
            }
            if (maxLen < len) maxLen = len;
        }
        return maxLen;
    }
}
